package org.algorithm.熊猫.字符串;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @date 2022-04-14 星期四 00:00
 * 输入：s1 = "ab" s2 = "eidbaooo"
 * 输出：true
 * 解释：s2 包含 s1 的排列之一 ("ba").
 * 示例 2：
 * <p>
 * 输入：s1= "ab" s2 = "eidboaoo"
 * 输出：false
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutation-in-string
 */
public class 字符串的排列2 {
    @Test
    public void test() {
        String replace = "aaaa".replaceFirst("a", "b");
        System.out.println(replace);
    }

    public boolean checkInclusion2(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < n; ++i) {
            ++cnt1[s1.charAt(i) - 'a'];
            ++cnt2[s2.charAt(i) - 'a'];
        }
        if (Arrays.equals(cnt1, cnt2)) {
            return true;
        }
        for (int i = n; i < m; ++i) {
            ++cnt2[s2.charAt(i) - 'a'];
            --cnt2[s2.charAt(i - n) - 'a'];
            if (Arrays.equals(cnt1, cnt2)) {
                return true;
            }
        }
        return false;
    }



    public String[] permutation(String s) {
        // 记录回溯算法的递归路径
        StringBuilder track = new StringBuilder();
        // 「路径」中的元素会被标记为 true，避免重复使⽤
        boolean[] used = new boolean[s.length()];

        char[] nums = s.toCharArray();
        Arrays.sort(nums);
        backtrack(nums, track, used);
        System.out.println(res);
        return res.toArray(new String[0]);
    }


    ArrayList<String> res = new ArrayList<>();


    // 回溯算法核⼼函数，遍历⼦集问题的回溯树
    void backtrack(char[] nums, StringBuilder track, boolean[] used) {
        if (track.length() == nums.length) {
            res.add(track.toString());
            return;
        }
        // 回溯算法标准框架
        //记录前一个元素
        char preChar = (char) -1000;
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                //当前数值已经在路径中
                continue;
            }
            //去重
            if (nums[i] == preChar) {
                continue;
            }
            preChar = nums[i];
            // 做选择
            track.append(nums[i]);
            // 通过 used 参数控制经过的路径，避免路径走岔
            used[i] = true;
            backtrack(nums, track, used);
            // 撤销选择
            used[i] = false;
            if (track.length() > 0) track.deleteCharAt(track.length() - 1);
        }
    }

}
